package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Lc210 {


    //拓朴排序
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>(); //list[i] 记录课程i的后续课程
        for (int i = 0; i < numCourses; i ++) {
            adjacency.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int u = prerequisites[i][0];
            int v = prerequisites[i][1]; // v->u
            indegree[u] ++;
            adjacency.get(v).add(u);
        }
        int[] ans = new int[numCourses];
        int cnt = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            ans[cnt++] = u;
            List<Integer> list = adjacency.get(u); //获取u的后继节点
            for (int i = 0; i < list.size(); i++) {
                if (--indegree[list.get(i)] == 0) {
                    queue.offer(list.get(i));
                }
            }
        }
        if (cnt == numCourses) //判断是否能进行拓朴排序
            return ans;
        return new int[]{};
    }













}
